
class Solution:
    def numIslands(self, grid) -> int:
        def _dfs(grid, i, j):
            if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0': return
            grid[i][j] = '0'
            _dfs(grid, i + 1, j)
            _dfs(grid, i, j + 1)
            _dfs(grid, i - 1, j)
            _dfs(grid, i, j - 1)
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    _dfs(grid, i, j)
                    count += 1
        return count

if __name__ == '__main__':
    s = Solution()
    grid = [
        ["1","1","1","1","0"],
        ["1","1","0","1","0"],
        ["1","1","0","0","0"],
        ["0","0","0","0","0"]
    ]
    print(s.numIslands(grid))
    